<!DOCTYPE html>
<html lang="" xml:lang="">
<head>

  <meta charset="utf-8" />
  <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  <title>leetcode</title>
  <meta name="description" content="leetcode" />
  <meta name="generator" content="bookdown #bookdown:version# and GitBook 2.6.7" />

  <meta property="og:title" content="leetcode" />
  <meta property="og:type" content="book" />
  
  
  
  

  <meta name="twitter:card" content="summary" />
  <meta name="twitter:title" content="leetcode" />
  
  
  

<meta name="author" content="高文欣" />


<meta name="date" content="2020-05-21" />

  <meta name="viewport" content="width=device-width, initial-scale=1" />
  <meta name="apple-mobile-web-app-capable" content="yes" />
  <meta name="apple-mobile-web-app-status-bar-style" content="black" />
  
  
<!--bookdown:link_prev-->
<!--bookdown:link_next-->
<script src="libs/jquery-2.2.3/jquery.min.js"></script>
<link href="libs/gitbook-2.6.7/css/style.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-table.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-bookdown.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-highlight.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-search.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-fontsettings.css" rel="stylesheet" />
<link href="libs/gitbook-2.6.7/css/plugin-clipboard.css" rel="stylesheet" />
<script src="libs/gitbook-2.6.7/js/app.min.js"></script>
<script src="libs/gitbook-2.6.7/js/lunr.js"></script>
<script src="libs/gitbook-2.6.7/js/clipboard.min.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-search.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-sharing.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-fontsettings.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-bookdown.js"></script>
<script src="libs/gitbook-2.6.7/js/jquery.highlight.js"></script>
<script src="libs/gitbook-2.6.7/js/plugin-clipboard.js"></script>
<link href="libs/pagedtable-1.1/css/pagedtable.css" rel="stylesheet" />
<script src="libs/pagedtable-1.1/js/pagedtable.js"></script>


<style type="text/css">
code.sourceCode > span { display: inline-block; line-height: 1.25; }
code.sourceCode > span { color: inherit; text-decoration: inherit; }
code.sourceCode > span:empty { height: 1.2em; }
.sourceCode { overflow: visible; }
code.sourceCode { white-space: pre; position: relative; }
div.sourceCode { margin: 1em 0; }
pre.sourceCode { margin: 0; }
@media screen {
div.sourceCode { overflow: auto; }
}
@media print {
code.sourceCode { white-space: pre-wrap; }
code.sourceCode > span { text-indent: -5em; padding-left: 5em; }
}
pre.numberSource code
  { counter-reset: source-line 0; }
pre.numberSource code > span
  { position: relative; left: -4em; counter-increment: source-line; }
pre.numberSource code > span > a:first-child::before
  { content: counter(source-line);
    position: relative; left: -1em; text-align: right; vertical-align: baseline;
    border: none; display: inline-block;
    -webkit-touch-callout: none; -webkit-user-select: none;
    -khtml-user-select: none; -moz-user-select: none;
    -ms-user-select: none; user-select: none;
    padding: 0 4px; width: 4em;
    color: #aaaaaa;
  }
pre.numberSource { margin-left: 3em; border-left: 1px solid #aaaaaa;  padding-left: 4px; }
div.sourceCode
  {   }
@media screen {
code.sourceCode > span > a:first-child::before { text-decoration: underline; }
}
code span.al { color: #ff0000; font-weight: bold; } /* Alert */
code span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */
code span.at { color: #7d9029; } /* Attribute */
code span.bn { color: #40a070; } /* BaseN */
code span.bu { } /* BuiltIn */
code span.cf { color: #007020; font-weight: bold; } /* ControlFlow */
code span.ch { color: #4070a0; } /* Char */
code span.cn { color: #880000; } /* Constant */
code span.co { color: #60a0b0; font-style: italic; } /* Comment */
code span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */
code span.do { color: #ba2121; font-style: italic; } /* Documentation */
code span.dt { color: #902000; } /* DataType */
code span.dv { color: #40a070; } /* DecVal */
code span.er { color: #ff0000; font-weight: bold; } /* Error */
code span.ex { } /* Extension */
code span.fl { color: #40a070; } /* Float */
code span.fu { color: #06287e; } /* Function */
code span.im { } /* Import */
code span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */
code span.kw { color: #007020; font-weight: bold; } /* Keyword */
code span.op { color: #666666; } /* Operator */
code span.ot { color: #007020; } /* Other */
code span.pp { color: #bc7a00; } /* Preprocessor */
code span.sc { color: #4070a0; } /* SpecialChar */
code span.ss { color: #bb6688; } /* SpecialString */
code span.st { color: #4070a0; } /* String */
code span.va { color: #19177c; } /* Variable */
code span.vs { color: #4070a0; } /* VerbatimString */
code span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */
</style>

</head>

<body>



<!--bookdown:title:start-->
<div id="header">
<h1 class="title">leetcode</h1>
<p class="author"><em>高文欣</em></p>
<p class="date"><em>2020-05-21</em></p>
</div>
<!--bookdown:title:end-->

<!--bookdown:toc:start-->
  <div class="book without-animation with-summary font-size-2 font-family-1" data-basepath=".">

    <div class="book-summary">
      <nav role="navigation">
<!--bookdown:toc2:start-->
<ul>
<li><a href="#数据结构与算法"><span class="toc-section-number">1</span> 数据结构与算法</a><ul>
<li><a href="#拓扑排序"><span class="toc-section-number">1.1</span> 拓扑排序</a></li>
<li><a href="#大经典排序算法"><span class="toc-section-number">1.2</span> 10大经典排序算法</a></li>
<li><a href="#时间复杂度"><span class="toc-section-number">1.3</span> 时间复杂度</a><ul>
<li><a href="#快速排序"><span class="toc-section-number">1.3.1</span> 快速排序</a></li>
<li><a href="#归并排序"><span class="toc-section-number">1.3.2</span> 归并排序</a></li>
</ul></li>
<li><a href="#二叉树问题"><span class="toc-section-number">1.4</span> 二叉树问题</a><ul>
<li><a href="#相同的树"><span class="toc-section-number">1.4.1</span> 相同的树</a></li>
<li><a href="#对称二叉树"><span class="toc-section-number">1.4.2</span> 对称二叉树</a></li>
<li><a href="#二叉树的最大深度"><span class="toc-section-number">1.4.3</span> 二叉树的最大深度</a></li>
<li><a href="#二叉树的最小深度"><span class="toc-section-number">1.4.4</span> 二叉树的最小深度</a></li>
<li><a href="#二叉树的层次遍历"><span class="toc-section-number">1.4.5</span> 二叉树的层次遍历</a></li>
<li><a href="#python切片复习"><span class="toc-section-number">1.4.6</span> python切片复习</a></li>
<li><a href="#将有序数组"><span class="toc-section-number">1.4.7</span> 将有序数组</a></li>
<li><a href="#平衡二叉树"><span class="toc-section-number">1.4.8</span> 平衡二叉树</a></li>
<li><a href="#路径总和"><span class="toc-section-number">1.4.9</span> 路径总和</a></li>
<li><a href="#翻转二叉树"><span class="toc-section-number">1.4.10</span> 翻转二叉树</a></li>
<li><a href="#公共祖先"><span class="toc-section-number">1.4.11</span> 公共祖先</a></li>
<li><a href="#二叉树的所有路径"><span class="toc-section-number">1.4.12</span> 二叉树的所有路径</a></li>
<li><a href="#左叶子之和"><span class="toc-section-number">1.4.13</span> 左叶子之和</a></li>
<li><a href="#路径总和-1"><span class="toc-section-number">1.4.14</span> 路径总和</a></li>
</ul></li>
<li><a href="#动态规划问题"><span class="toc-section-number">1.5</span> 动态规划问题</a><ul>
<li><a href="#买卖股票的最佳时机"><span class="toc-section-number">1.5.1</span> 买卖股票的最佳时机</a></li>
<li><a href="#爬楼梯问题"><span class="toc-section-number">1.5.2</span> 爬楼梯问题</a></li>
<li><a href="#最大子序和问题"><span class="toc-section-number">1.5.3</span> 最大子序和问题</a></li>
<li><a href="#偷钱问题"><span class="toc-section-number">1.5.4</span> 偷钱问题</a></li>
<li><a href="#比特位计数"><span class="toc-section-number">1.5.5</span> 比特位计数</a></li>
<li><a href="#最短路径和问题"><span class="toc-section-number">1.5.6</span> 最短路径和问题</a></li>
<li><a href="#回文字符串"><span class="toc-section-number">1.5.7</span> 回文字符串</a></li>
</ul></li>
<li><a href="#哈希表"><span class="toc-section-number">1.6</span> 哈希表</a><ul>
<li><a href="#k数之和"><span class="toc-section-number">1.6.1</span> K数之和</a></li>
</ul></li>
<li><a href="#贪心算法"><span class="toc-section-number">1.7</span> 贪心算法</a><ul>
<li><a href="#跳跃游戏"><span class="toc-section-number">1.7.1</span> 跳跃游戏</a></li>
</ul></li>
</ul></li>
</ul>
<!--bookdown:toc2:end-->
      </nav>
    </div>

    <div class="book-body">
      <div class="body-inner">
        <div class="book-header" role="navigation">
          <h1>
            <i class="fa fa-circle-o-notch fa-spin"></i><a href="./">leetcode</a>
          </h1>
        </div>

        <div class="page-wrapper" tabindex="-1" role="main">
          <div class="page-inner">

            <section class="normal" id="section-">
<!--bookdown:toc:end-->
<!--bookdown:body:start-->
<div id="数据结构与算法" class="section level1">
<h1><span class="header-section-number">1</span> 数据结构与算法</h1>
<p>数据结构的基础知识</p>
<blockquote>
<p>栈：后进先出（LIFO-last in first out）:最后插入的元素最先出来。
队列：先进先出（FIFO-first in first out）:最先插入的元素最先出来。</p>
</blockquote>
<div id="拓扑排序" class="section level2">
<h2><span class="header-section-number">1.1</span> 拓扑排序</h2>
<p>遍历一个有向无环图
<em>入度</em>:指向该顶点的边
<em>出度</em>:从该顶点发出的边</p>
<p>最经典的例子:先修课</p>
<p>拓扑排序，维持一个入度为0的队列即可。</p>
<p><a href="https://mp.weixin.qq.com/s?__biz=MzA3MjU5NjU2NA==&amp;mid=2455502896&amp;idx=1&amp;sn=df6f2c86e0f1de823f79087ba9e8eb33&amp;chksm=88b34d0bbfc4c41d863b4b6d78309e6ae01e766b1a7826b4c326246dd2489df9d684e8091ece&amp;scene=21#wechat_redirect">拓扑排序</a></p>
</div>
<div id="大经典排序算法" class="section level2">
<h2><span class="header-section-number">1.2</span> 10大经典排序算法</h2>
</div>
<div id="时间复杂度" class="section level2">
<h2><span class="header-section-number">1.3</span> 时间复杂度</h2>
<p>稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机</p>
<div class="figure">
<img src="figs/时间复杂度与空间复杂度.jpg" alt="" />
<p class="caption">时间复杂度与空间复杂度</p>
</div>
<p><a href="https://mp.weixin.qq.com/s/Yp1hD2Bbmj3pRrLYjfwfEw">10大经典排序python实现</a></p>
<p>两个不太好记的</p>
<div id="快速排序" class="section level3">
<h3><span class="header-section-number">1.3.1</span> 快速排序</h3>
<p>基准大法</p>
<p>基准左边的都不大于它，基准右边的都不小于它
左右两边一起搜索交换<a href="https://www.jianshu.com/p/55ab254586bf">jianzhu</a></p>
<p>从左边开始找到一个比它大的数，从右边往左找到一个比它小的数，交换位置</p>
<blockquote>
<p>冒泡排序的特点是每次都比较相邻的两个数字，每次位置互换，也只能换一个跨度。 快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。</p>
</blockquote>
<div class="sourceCode" id="cb1"><pre class="sourceCode python"><code class="sourceCode python"><span id="cb1-1"><a href="#cb1-1"></a><span class="kw">def</span> quickSort(arr, left<span class="op">=</span><span class="va">None</span>, right<span class="op">=</span><span class="va">None</span>):</span>
<span id="cb1-2"><a href="#cb1-2"></a>    left <span class="op">=</span> <span class="dv">0</span> <span class="cf">if</span> <span class="kw">not</span> <span class="bu">isinstance</span>(left,(<span class="bu">int</span>, <span class="bu">float</span>)) <span class="cf">else</span> left</span>
<span id="cb1-3"><a href="#cb1-3"></a>    right <span class="op">=</span> <span class="bu">len</span>(arr)<span class="op">-</span><span class="dv">1</span> <span class="cf">if</span> <span class="kw">not</span> <span class="bu">isinstance</span>(right,(<span class="bu">int</span>, <span class="bu">float</span>)) <span class="cf">else</span> right</span>
<span id="cb1-4"><a href="#cb1-4"></a>    <span class="cf">if</span> left <span class="op">&lt;</span> right:</span>
<span id="cb1-5"><a href="#cb1-5"></a>        partitionIndex <span class="op">=</span> partition(arr, left, right)</span>
<span id="cb1-6"><a href="#cb1-6"></a>        quickSort(arr, left, partitionIndex<span class="dv">-1</span>)</span>
<span id="cb1-7"><a href="#cb1-7"></a>        quickSort(arr, partitionIndex<span class="op">+</span><span class="dv">1</span>, right)</span>
<span id="cb1-8"><a href="#cb1-8"></a>    <span class="cf">return</span> arr</span>
<span id="cb1-9"><a href="#cb1-9"></a></span>
<span id="cb1-10"><a href="#cb1-10"></a><span class="kw">def</span> partition(arr, left, right):</span>
<span id="cb1-11"><a href="#cb1-11"></a>    pivot <span class="op">=</span> left</span>
<span id="cb1-12"><a href="#cb1-12"></a>    index <span class="op">=</span> pivot<span class="op">+</span><span class="dv">1</span></span>
<span id="cb1-13"><a href="#cb1-13"></a>    i <span class="op">=</span> index</span>
<span id="cb1-14"><a href="#cb1-14"></a>    <span class="cf">while</span>  i <span class="op">&lt;=</span> right:</span>
<span id="cb1-15"><a href="#cb1-15"></a>        <span class="cf">if</span> arr[i] <span class="op">&lt;</span> arr[pivot]:</span>
<span id="cb1-16"><a href="#cb1-16"></a>            swap(arr, i, index)</span>
<span id="cb1-17"><a href="#cb1-17"></a>            index<span class="op">+=</span><span class="dv">1</span></span>
<span id="cb1-18"><a href="#cb1-18"></a>        i<span class="op">+=</span><span class="dv">1</span></span>
<span id="cb1-19"><a href="#cb1-19"></a>    swap(arr,pivot,index<span class="dv">-1</span>)<span class="co">#left往右，index往左，就是这里要理解</span></span>
<span id="cb1-20"><a href="#cb1-20"></a>    <span class="cf">return</span> index<span class="dv">-1</span></span>
<span id="cb1-21"><a href="#cb1-21"></a></span>
<span id="cb1-22"><a href="#cb1-22"></a><span class="kw">def</span> swap(arr, i, j):</span>
<span id="cb1-23"><a href="#cb1-23"></a>    arr[i], arr[j] <span class="op">=</span> arr[j], arr[i]</span></code></pre></div>
<ul>
<li><strong>这个方法更好理解，也简单一些</strong></li>
</ul>
<div class="sourceCode" id="cb2"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb2-1"><a href="#cb2-1"></a>def <span class="kw">quick_sort</span>(data)<span class="op">:</span><span class="st">    </span></span>
<span id="cb2-2"><a href="#cb2-2"></a><span class="st">    &quot;&quot;&quot;快速排序&quot;&quot;&quot;</span>    </span>
<span id="cb2-3"><a href="#cb2-3"></a>    <span class="cf">if</span> <span class="kw">len</span>(data) <span class="op">&gt;=</span><span class="st"> </span><span class="dv">2</span><span class="op">:</span><span class="st">  </span><span class="co"># 递归入口及出口        </span></span>
<span id="cb2-4"><a href="#cb2-4"></a><span class="st">        </span>mid =<span class="st"> </span>data[<span class="kw">len</span>(data)<span class="op">/</span><span class="er">/</span><span class="dv">2</span>]  <span class="co"># 选取基准值，也可以选取第一个或最后一个元素        </span></span>
<span id="cb2-5"><a href="#cb2-5"></a>        left, right =<span class="st"> </span>[], []  <span class="co"># 定义基准值左右两侧的列表        </span></span>
<span id="cb2-6"><a href="#cb2-6"></a>        <span class="kw">data.remove</span>(mid)  <span class="co"># 从原始数组中移除基准值        </span></span>
<span id="cb2-7"><a href="#cb2-7"></a>        <span class="cf">for</span> num <span class="cf">in</span> data<span class="op">:</span><span class="st">            </span></span>
<span id="cb2-8"><a href="#cb2-8"></a><span class="st">            </span><span class="cf">if</span> num <span class="op">&gt;=</span><span class="st"> </span>mid<span class="op">:</span><span class="st">                </span></span>
<span id="cb2-9"><a href="#cb2-9"></a><span class="st">                </span><span class="kw">right.append</span>(num)            </span>
<span id="cb2-10"><a href="#cb2-10"></a>            <span class="cf">else</span><span class="op">:</span><span class="st">                </span></span>
<span id="cb2-11"><a href="#cb2-11"></a><span class="st">                </span><span class="kw">left.append</span>(num)        </span>
<span id="cb2-12"><a href="#cb2-12"></a>        return <span class="kw">quick_sort</span>(left) <span class="op">+</span><span class="st"> </span>[mid] <span class="op">+</span><span class="st"> </span><span class="kw">quick_sort</span>(right)    </span>
<span id="cb2-13"><a href="#cb2-13"></a>    <span class="cf">else</span><span class="op">:</span><span class="st">        </span></span>
<span id="cb2-14"><a href="#cb2-14"></a><span class="st">        </span>return data</span></code></pre></div>
<p>快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。
理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。
最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。
为改善最坏情况下的时间性能，可采用其他方法选取中间数。通常采用“三者值取中”方法，即比较H-&gt;r[low].key、H-&gt;r[high].key与H-&gt;r[(10w+high)/2].key，取三者中关键字为中值的元素为中间数。
可以证明，快速排序的平均时间复杂度也是O(nlog2n)。因此，该排序方法被认为是目前最好的一种内部排序方法。
从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log2(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(log2n))</p>
<ul>
<li>isinstance</li>
</ul>
<blockquote>
<p>The isinstance() function checks if the object (first argument) is an instance or subclass of classinfo class (second argument).</p>
</blockquote>
<p>判断第一个参数变量是否是第二个参数的类型</p>
</div>
<div id="归并排序" class="section level3">
<h3><span class="header-section-number">1.3.2</span> 归并排序</h3>
<p>分而治之</p>
<div class="sourceCode" id="cb3"><pre class="sourceCode python"><code class="sourceCode python"><span id="cb3-1"><a href="#cb3-1"></a><span class="kw">def</span> mergeSort(arr):</span>
<span id="cb3-2"><a href="#cb3-2"></a>    <span class="im">import</span> math</span>
<span id="cb3-3"><a href="#cb3-3"></a>    <span class="cf">if</span>(<span class="bu">len</span>(arr)<span class="op">&lt;</span><span class="dv">2</span>):</span>
<span id="cb3-4"><a href="#cb3-4"></a>        <span class="cf">return</span> arr</span>
<span id="cb3-5"><a href="#cb3-5"></a>    middle <span class="op">=</span> math.floor(<span class="bu">len</span>(arr)<span class="op">/</span><span class="dv">2</span>)</span>
<span id="cb3-6"><a href="#cb3-6"></a>    left, right <span class="op">=</span> arr[<span class="dv">0</span>:middle], arr[middle:]</span>
<span id="cb3-7"><a href="#cb3-7"></a>    <span class="cf">return</span> merge(mergeSort(left), mergeSort(right))</span>
<span id="cb3-8"><a href="#cb3-8"></a></span>
<span id="cb3-9"><a href="#cb3-9"></a><span class="kw">def</span> merge(left,right):</span>
<span id="cb3-10"><a href="#cb3-10"></a>    result <span class="op">=</span> [] <span class="co">#定义一个空列表追加元素</span></span>
<span id="cb3-11"><a href="#cb3-11"></a>    <span class="cf">while</span> left <span class="kw">and</span> right:</span>
<span id="cb3-12"><a href="#cb3-12"></a>        <span class="cf">if</span> left[<span class="dv">0</span>] <span class="op">&lt;=</span> right[<span class="dv">0</span>]:</span>
<span id="cb3-13"><a href="#cb3-13"></a>            result.append(left.pop(<span class="dv">0</span>))<span class="op">;</span></span>
<span id="cb3-14"><a href="#cb3-14"></a>        <span class="cf">else</span>:</span>
<span id="cb3-15"><a href="#cb3-15"></a>            result.append(right.pop(<span class="dv">0</span>))<span class="op">;</span></span>
<span id="cb3-16"><a href="#cb3-16"></a>    <span class="cf">while</span> left:</span>
<span id="cb3-17"><a href="#cb3-17"></a>        result.append(left.pop(<span class="dv">0</span>))<span class="op">;</span></span>
<span id="cb3-18"><a href="#cb3-18"></a>    <span class="cf">while</span> right:</span>
<span id="cb3-19"><a href="#cb3-19"></a>        result.append(right.pop(<span class="dv">0</span>))<span class="op">;</span></span>
<span id="cb3-20"><a href="#cb3-20"></a>    <span class="cf">return</span> result</span></code></pre></div>
<p>pop函数的用法</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb4-1"><a href="#cb4-1"></a>a=[<span class="st">&#39;1&#39;</span>,<span class="st">&#39;2&#39;</span>,<span class="st">&#39;3&#39;</span>]</span>
<span id="cb4-2"><a href="#cb4-2"></a>d=<span class="kw">a.pop</span>(<span class="dv">0</span>)</span>
<span id="cb4-3"><a href="#cb4-3"></a>d</span>
<span id="cb4-4"><a href="#cb4-4"></a><span class="co"># 1</span></span></code></pre></div>
</div>
</div>
<div id="二叉树问题" class="section level2">
<h2><span class="header-section-number">1.4</span> 二叉树问题</h2>
<ul>
<li>root.val是该节点的值。</li>
<li>root则相当于指向该节点的指针。</li>
<li>root.left, root.right指向其左右节点的位置</li>
</ul>
<p>val=values
left,right就是位置</p>
<p><a href="https://zhuanlan.zhihu.com/p/63419145">知乎</a></p>
<div id="相同的树" class="section level3">
<h3><span class="header-section-number">1.4.1</span> 相同的树</h3>
<p>解题思路：两个树的结构相同，节点相同则相同,或者都为空也相同
递归
假入有2棵树p,q</p>
<div class="sourceCode" id="cb5"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb5-1"><a href="#cb5-1"></a>class <span class="kw">Solution</span>(object)<span class="op">:</span></span>
<span id="cb5-2"><a href="#cb5-2"></a><span class="st">    </span>def <span class="kw">isSameTree</span>(self, p, q)<span class="op">:</span></span>
<span id="cb5-3"><a href="#cb5-3"></a></span>
<span id="cb5-4"><a href="#cb5-4"></a><span class="st">        </span><span class="cf">if</span> p is None and q is None<span class="op">:</span></span>
<span id="cb5-5"><a href="#cb5-5"></a><span class="st">            </span>return True</span>
<span id="cb5-6"><a href="#cb5-6"></a>        <span class="cf">if</span> p is not None and q is not None<span class="op">:</span></span>
<span id="cb5-7"><a href="#cb5-7"></a><span class="st">            </span>return p.val<span class="op">==</span>q.val and <span class="kw">self.isSameTree</span>(p.left,q.left) and <span class="kw">self.isSameTree</span>(p.right,q.right)</span>
<span id="cb5-8"><a href="#cb5-8"></a>        return False</span></code></pre></div>
</div>
<div id="对称二叉树" class="section level3">
<h3><span class="header-section-number">1.4.2</span> 对称二叉树</h3>
<blockquote>
<p>首先判断头结点是否为空。然后<strong>将根节点的左右两个节点假设成两个独立的树</strong>，如果左右两个树都为空，返回True。然后看左子树的左结点和右子树的右结点、左子树的右结点和右子树的左结点是否相同，都相同返回True.</p>
</blockquote>
<div class="sourceCode" id="cb6"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb6-1"><a href="#cb6-1"></a>class <span class="kw">Solution</span>(object)<span class="op">:</span></span>
<span id="cb6-2"><a href="#cb6-2"></a><span class="st">    </span>def <span class="kw">isSymmetric</span>(self, root)<span class="op">:</span></span>
<span id="cb6-3"><a href="#cb6-3"></a></span>
<span id="cb6-4"><a href="#cb6-4"></a><span class="st">        </span><span class="cf">if</span> root is None<span class="op">:</span></span>
<span id="cb6-5"><a href="#cb6-5"></a><span class="st">            </span>return True</span>
<span id="cb6-6"><a href="#cb6-6"></a>        return <span class="kw">self.isSymmetricTree</span>(root.left,root.right)</span>
<span id="cb6-7"><a href="#cb6-7"></a>    def <span class="kw">isSymmetricTree</span>(self,left,right)<span class="op">:</span></span>
<span id="cb6-8"><a href="#cb6-8"></a><span class="st">        </span><span class="cf">if</span> left is None and right is None<span class="op">:</span></span>
<span id="cb6-9"><a href="#cb6-9"></a><span class="st">            </span>return True</span>
<span id="cb6-10"><a href="#cb6-10"></a>        <span class="cf">if</span> left is None or right is None or left.val <span class="op">!=</span><span class="st"> </span>right.val<span class="op">:</span></span>
<span id="cb6-11"><a href="#cb6-11"></a><span class="st">            </span>return False</span>
<span id="cb6-12"><a href="#cb6-12"></a>        return <span class="kw">self.isSymmetricTree</span>(left.left,right.right) and <span class="kw">self.isSymmetricTree</span>(left.right,right.left)</span></code></pre></div>
</div>
<div id="二叉树的最大深度" class="section level3">
<h3><span class="header-section-number">1.4.3</span> 二叉树的最大深度</h3>
<p>二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。</p>
<div class="sourceCode" id="cb7"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb7-1"><a href="#cb7-1"></a>class <span class="kw">Solution</span>(object)<span class="op">:</span></span>
<span id="cb7-2"><a href="#cb7-2"></a><span class="st">    </span>def <span class="kw">maxDepth</span>(self, root)<span class="op">:</span></span>
<span id="cb7-3"><a href="#cb7-3"></a></span>
<span id="cb7-4"><a href="#cb7-4"></a><span class="st">        </span><span class="cf">if</span> root is None<span class="op">:</span></span>
<span id="cb7-5"><a href="#cb7-5"></a><span class="st">            </span>return <span class="dv">0</span></span>
<span id="cb7-6"><a href="#cb7-6"></a>        <span class="cf">else</span><span class="op">:</span></span>
<span id="cb7-7"><a href="#cb7-7"></a><span class="st">            </span>return <span class="kw">max</span>(<span class="kw">self.maxDepth</span>(root.left),<span class="kw">self.maxDepth</span>(root.right))<span class="op">+</span><span class="dv">1</span></span></code></pre></div>
</div>
<div id="二叉树的最小深度" class="section level3">
<h3><span class="header-section-number">1.4.4</span> 二叉树的最小深度</h3>
<p>最小深度是从根节点到最近叶子节点的最短路径上的节点数量。</p>
<div class="sourceCode" id="cb8"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb8-1"><a href="#cb8-1"></a>class <span class="kw">Solution</span>(object)<span class="op">:</span></span>
<span id="cb8-2"><a href="#cb8-2"></a><span class="st">    </span>def <span class="kw">minDepth</span>(self, root)<span class="op">:</span></span>
<span id="cb8-3"><a href="#cb8-3"></a><span class="st">       </span></span>
<span id="cb8-4"><a href="#cb8-4"></a><span class="st">        </span><span class="cf">if</span> root is None<span class="op">:</span></span>
<span id="cb8-5"><a href="#cb8-5"></a><span class="st">            </span>return <span class="dv">0</span></span>
<span id="cb8-6"><a href="#cb8-6"></a>        <span class="cf">if</span> root.left and root.right<span class="op">:</span></span>
<span id="cb8-7"><a href="#cb8-7"></a><span class="st">            </span>return <span class="kw">min</span>(<span class="kw">self.minDepth</span>(root.left),<span class="kw">self.minDepth</span>(root.right))<span class="op">+</span><span class="dv">1</span></span>
<span id="cb8-8"><a href="#cb8-8"></a>        <span class="cf">else</span><span class="op">:</span></span>
<span id="cb8-9"><a href="#cb8-9"></a><span class="st">            </span>return <span class="kw">max</span>(<span class="kw">self.minDepth</span>(root.left),<span class="kw">self.minDepth</span>(root.right))<span class="op">+</span><span class="dv">1</span> <span class="co">#根节点只有一个节点的时候</span></span></code></pre></div>
</div>
<div id="二叉树的层次遍历" class="section level3">
<h3><span class="header-section-number">1.4.5</span> 二叉树的层次遍历</h3>
<p>给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）</p>
<p>定义两个数组，一个level的，一个level装节点的</p>
<div class="sourceCode" id="cb9"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb9-1"><a href="#cb9-1"></a>class <span class="kw">Solution</span>(object)<span class="op">:</span></span>
<span id="cb9-2"><a href="#cb9-2"></a><span class="st">    </span>def <span class="kw">levelOrderBottom</span>(self, root)<span class="op">:</span></span>
<span id="cb9-3"><a href="#cb9-3"></a></span>
<span id="cb9-4"><a href="#cb9-4"></a><span class="st">        </span><span class="cf">if</span> root is None<span class="op">:</span><span class="st"> </span><span class="co">#根节点不为空</span></span>
<span id="cb9-5"><a href="#cb9-5"></a><span class="st">            </span>return []</span>
<span id="cb9-6"><a href="#cb9-6"></a>        </span>
<span id="cb9-7"><a href="#cb9-7"></a>        result,current =<span class="st"> </span>[],[root] <span class="co">#当前节点在root</span></span>
<span id="cb9-8"><a href="#cb9-8"></a>        </span>
<span id="cb9-9"><a href="#cb9-9"></a>        <span class="cf">while</span> current<span class="op">:</span></span>
<span id="cb9-10"><a href="#cb9-10"></a><span class="st">            </span>next_level,vals =<span class="st"> </span>[], []</span>
<span id="cb9-11"><a href="#cb9-11"></a>            <span class="cf">for</span> node <span class="cf">in</span> current<span class="op">:</span></span>
<span id="cb9-12"><a href="#cb9-12"></a><span class="st">                </span><span class="kw">vals.append</span>(node.val)</span>
<span id="cb9-13"><a href="#cb9-13"></a>                <span class="cf">if</span> node.left<span class="op">:</span></span>
<span id="cb9-14"><a href="#cb9-14"></a><span class="st">                    </span><span class="kw">next_level.append</span>(node.left)</span>
<span id="cb9-15"><a href="#cb9-15"></a>                <span class="cf">if</span> node.right<span class="op">:</span></span>
<span id="cb9-16"><a href="#cb9-16"></a><span class="st">                    </span><span class="kw">next_level.append</span>(node.right)</span>
<span id="cb9-17"><a href="#cb9-17"></a>            current =<span class="st"> </span>next_level</span>
<span id="cb9-18"><a href="#cb9-18"></a>            <span class="kw">result.append</span>(vals)</span>
<span id="cb9-19"><a href="#cb9-19"></a>        return result[<span class="op">::-</span><span class="dv">1</span>] <span class="co">#从低向上</span></span></code></pre></div>
</div>
<div id="python切片复习" class="section level3">
<h3><span class="header-section-number">1.4.6</span> python切片复习</h3>
<p>object[start_index:end_index:step]
step为正就是从左往右取值
step为负就是从右往左取值
不包括end_index
参考<a href="https://www.jianshu.com/p/15715d6f4dad">csdn</a></p>
<div class="sourceCode" id="cb10"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb10-1"><a href="#cb10-1"></a>a=[<span class="st">&#39;1&#39;</span>,<span class="st">&#39;2&#39;</span>,<span class="st">&#39;3&#39;</span>]</span>
<span id="cb10-2"><a href="#cb10-2"></a>c=a[<span class="op">::-</span><span class="dv">1</span>]</span>
<span id="cb10-3"><a href="#cb10-3"></a>c</span>
<span id="cb10-4"><a href="#cb10-4"></a><span class="co">#[&#39;3&#39;, &#39;2&#39;, &#39;1&#39;]</span></span></code></pre></div>
<p>需要记住的几个</p>
<div class="sourceCode" id="cb11"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb11-1"><a href="#cb11-1"></a>a =<span class="st"> </span>[<span class="dv">0</span>, <span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>, <span class="dv">5</span>, <span class="dv">6</span>, <span class="dv">7</span>, <span class="dv">8</span>, <span class="dv">9</span>]</span>
<span id="cb11-2"><a href="#cb11-2"></a></span>
<span id="cb11-3"><a href="#cb11-3"></a><span class="op">&gt;</span><span class="er">&gt;&gt;</span>a[<span class="op">:</span>] <span class="co">#从左往右</span></span>
<span id="cb11-4"><a href="#cb11-4"></a><span class="op">&gt;</span><span class="er">&gt;&gt;</span><span class="st"> </span>[<span class="dv">0</span>, <span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>, <span class="dv">5</span>, <span class="dv">6</span>, <span class="dv">7</span>, <span class="dv">8</span>, <span class="dv">9</span>]</span>
<span id="cb11-5"><a href="#cb11-5"></a><span class="op">&gt;</span><span class="er">&gt;&gt;</span>a[<span class="op">::</span>]<span class="co">#从左往右</span></span>
<span id="cb11-6"><a href="#cb11-6"></a><span class="op">&gt;</span><span class="er">&gt;&gt;</span><span class="st"> </span>[<span class="dv">0</span>, <span class="dv">1</span>, <span class="dv">2</span>, <span class="dv">3</span>, <span class="dv">4</span>, <span class="dv">5</span>, <span class="dv">6</span>, <span class="dv">7</span>, <span class="dv">8</span>, <span class="dv">9</span>]</span>
<span id="cb11-7"><a href="#cb11-7"></a><span class="op">&gt;</span><span class="er">&gt;&gt;</span>a[<span class="op">::-</span><span class="dv">1</span>]<span class="co">#从右往左</span></span>
<span id="cb11-8"><a href="#cb11-8"></a><span class="op">&gt;</span><span class="er">&gt;&gt;</span><span class="st"> </span>[<span class="dv">9</span>, <span class="dv">8</span>, <span class="dv">7</span>, <span class="dv">6</span>, <span class="dv">5</span>, <span class="dv">4</span>, <span class="dv">3</span>, <span class="dv">2</span>, <span class="dv">1</span>, <span class="dv">0</span>]</span></code></pre></div>
</div>
<div id="将有序数组" class="section level3">
<h3><span class="header-section-number">1.4.7</span> 将有序数组</h3>
<p>转换为二叉搜索树</p>
<p><strong>取有序数组的中间节点作为根节点，将数组分为左右两个部分，对左右两个子数组做相同的操作，递归的实现</strong>。暴力取中间节点为root：递归实现</p>
<div class="sourceCode" id="cb12"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb12-1"><a href="#cb12-1"></a>class Solution<span class="op">:</span></span>
<span id="cb12-2"><a href="#cb12-2"></a><span class="st">    </span>def <span class="kw">sortedArrayToBST</span>(self, nums<span class="op">:</span><span class="st"> </span>List[int]) -&gt;<span class="st"> </span>TreeNode<span class="op">:</span></span>
<span id="cb12-3"><a href="#cb12-3"></a><span class="st">        </span><span class="cf">if</span> nums<span class="op">:</span></span>
<span id="cb12-4"><a href="#cb12-4"></a><span class="st">            </span>m =<span class="st"> </span><span class="kw">len</span>(nums) <span class="op">/</span><span class="er">/</span><span class="st"> </span><span class="dv">2</span> 中间节点为根节点</span>
<span id="cb12-5"><a href="#cb12-5"></a>            r =<span class="st"> </span><span class="kw">TreeNode</span>(nums[m])</span>
<span id="cb12-6"><a href="#cb12-6"></a>            r.left, r.right =<span class="st"> </span><span class="kw">map</span>(self.sortedArrayToBST, [nums[<span class="op">:</span>m], nums[m<span class="op">+</span><span class="dv">1</span><span class="op">:</span>]])</span>
<span id="cb12-7"><a href="#cb12-7"></a>            return r</span></code></pre></div>
</div>
<div id="平衡二叉树" class="section level3">
<h3><span class="header-section-number">1.4.8</span> 平衡二叉树</h3>
<p><strong>一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值小于1。</strong></p>
<div class="sourceCode" id="cb13"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb13-1"><a href="#cb13-1"></a>class <span class="kw">Solution</span>(object)<span class="op">:</span></span>
<span id="cb13-2"><a href="#cb13-2"></a><span class="st">    </span>def <span class="kw">isBalanced</span>(self, root)<span class="op">:</span></span>
<span id="cb13-3"><a href="#cb13-3"></a></span>
<span id="cb13-4"><a href="#cb13-4"></a><span class="st">        </span><span class="cf">if</span> root <span class="op">==</span><span class="st"> </span>None<span class="op">:</span></span>
<span id="cb13-5"><a href="#cb13-5"></a><span class="st">            </span>return True</span>
<span id="cb13-6"><a href="#cb13-6"></a>        elif <span class="kw">abs</span>(<span class="kw">self.height</span>(root.left)<span class="op">-</span><span class="kw">self.height</span>(root.right))<span class="op">&gt;</span><span class="dv">1</span><span class="op">:</span><span class="st"> </span><span class="co">#高度的绝对值之差大于1，不平衡</span></span>
<span id="cb13-7"><a href="#cb13-7"></a><span class="st">            </span>return False</span>
<span id="cb13-8"><a href="#cb13-8"></a>        <span class="cf">else</span><span class="op">:</span></span>
<span id="cb13-9"><a href="#cb13-9"></a><span class="st">            </span>return <span class="kw">self.isBalanced</span>(root.left) and <span class="kw">self.isBalanced</span>(root.right)</span>
<span id="cb13-10"><a href="#cb13-10"></a>    </span>
<span id="cb13-11"><a href="#cb13-11"></a>    def <span class="kw">height</span>(self,root)<span class="op">:</span><span class="st"> </span><span class="co">#判断是否为平衡</span></span>
<span id="cb13-12"><a href="#cb13-12"></a><span class="st">        </span><span class="cf">if</span> root <span class="op">==</span><span class="st"> </span>None<span class="op">:</span></span>
<span id="cb13-13"><a href="#cb13-13"></a><span class="st">            </span>return <span class="dv">0</span></span>
<span id="cb13-14"><a href="#cb13-14"></a>        <span class="cf">else</span><span class="op">:</span></span>
<span id="cb13-15"><a href="#cb13-15"></a><span class="st">            </span>return <span class="kw">max</span>(<span class="kw">self.height</span>(root.left),<span class="kw">self.height</span>(root.right))<span class="op">+</span><span class="st"> </span><span class="dv">1</span></span></code></pre></div>
</div>
<div id="路径总和" class="section level3">
<h3><span class="header-section-number">1.4.9</span> 路径总和</h3>
<p>给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。</p>
<p><strong>从上到下加起来，最后一个节点的值就等于sum-前面的和，且这个节点是叶子节点。</strong></p>
<div class="sourceCode" id="cb14"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb14-1"><a href="#cb14-1"></a>class <span class="kw">Solution</span>(object)<span class="op">:</span></span>
<span id="cb14-2"><a href="#cb14-2"></a><span class="st">    </span>def <span class="kw">hasPathSum</span>(self, root, sum)<span class="op">:</span></span>
<span id="cb14-3"><a href="#cb14-3"></a><span class="st">       </span></span>
<span id="cb14-4"><a href="#cb14-4"></a><span class="st">        </span><span class="cf">if</span> root is None<span class="op">:</span></span>
<span id="cb14-5"><a href="#cb14-5"></a><span class="st">            </span>return False</span>
<span id="cb14-6"><a href="#cb14-6"></a>        <span class="cf">if</span> root.left is None and root.right is None and root.val<span class="op">==</span>sum<span class="op">:</span></span>
<span id="cb14-7"><a href="#cb14-7"></a><span class="st">            </span>return True</span>
<span id="cb14-8"><a href="#cb14-8"></a>        <span class="cf">else</span><span class="op">:</span></span>
<span id="cb14-9"><a href="#cb14-9"></a><span class="st">            </span>return <span class="kw">self.hasPathSum</span>(root.left,sum<span class="op">-</span>root.val) or <span class="kw">self.hasPathSum</span>(root.right,sum<span class="op">-</span>root.val)</span></code></pre></div>
</div>
<div id="翻转二叉树" class="section level3">
<h3><span class="header-section-number">1.4.10</span> 翻转二叉树</h3>
<p>镜面对换</p>
<p>那就是交换左右节点喽</p>
<div class="sourceCode" id="cb15"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb15-1"><a href="#cb15-1"></a>class <span class="kw">Solution</span>(object)<span class="op">:</span></span>
<span id="cb15-2"><a href="#cb15-2"></a><span class="st">    </span>def <span class="kw">invertTree</span>(self, root)<span class="op">:</span></span>
<span id="cb15-3"><a href="#cb15-3"></a></span>
<span id="cb15-4"><a href="#cb15-4"></a><span class="st">        </span><span class="cf">if</span> root is not None<span class="op">:</span></span>
<span id="cb15-5"><a href="#cb15-5"></a><span class="st">            </span>root.left,root.right =<span class="st"> </span><span class="kw">self.invertTree</span>(root.right),<span class="kw">self.invertTree</span>(root.left)</span>
<span id="cb15-6"><a href="#cb15-6"></a>        return root</span></code></pre></div>
</div>
<div id="公共祖先" class="section level3">
<h3><span class="header-section-number">1.4.11</span> 公共祖先</h3>
<p>二叉搜索树的最近公共祖先</p>
<p>这个不太明白。。</p>
<p>哦哦哦，这是确定了树，按照此题分析就好了，哈哈，看树的结构，左子树均小于根节点的值，右子树均大于根节点的值</p>
<div class="figure">
<img src="figs/公共祖先.png" alt="" />
<p class="caption">公共祖先描述</p>
</div>
<div class="sourceCode" id="cb16"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb16-1"><a href="#cb16-1"></a><span class="co"># Definition for a binary tree node.</span></span>
<span id="cb16-2"><a href="#cb16-2"></a><span class="co"># class TreeNode(object):</span></span>
<span id="cb16-3"><a href="#cb16-3"></a><span class="co">#     def __init__(self, x):</span></span>
<span id="cb16-4"><a href="#cb16-4"></a><span class="co">#         self.val = x</span></span>
<span id="cb16-5"><a href="#cb16-5"></a><span class="co">#         self.left = None</span></span>
<span id="cb16-6"><a href="#cb16-6"></a><span class="co">#         self.right = None</span></span>
<span id="cb16-7"><a href="#cb16-7"></a></span>
<span id="cb16-8"><a href="#cb16-8"></a>class <span class="kw">Solution</span>(object)<span class="op">:</span></span>
<span id="cb16-9"><a href="#cb16-9"></a><span class="st">    </span>def <span class="kw">lowestCommonAncestor</span>(self, root, p, q)<span class="op">:</span></span>
<span id="cb16-10"><a href="#cb16-10"></a><span class="st">        &quot;&quot;&quot;</span></span>
<span id="cb16-11"><a href="#cb16-11"></a><span class="st">        :type root: TreeNode</span></span>
<span id="cb16-12"><a href="#cb16-12"></a><span class="st">        :type p: TreeNode</span></span>
<span id="cb16-13"><a href="#cb16-13"></a><span class="st">        :type q: TreeNode</span></span>
<span id="cb16-14"><a href="#cb16-14"></a><span class="st">        :rtype: TreeNode</span></span>
<span id="cb16-15"><a href="#cb16-15"></a><span class="st">        &quot;&quot;&quot;</span></span>
<span id="cb16-16"><a href="#cb16-16"></a>        pointer =<span class="st"> </span>root</span>
<span id="cb16-17"><a href="#cb16-17"></a>        <span class="cf">while</span> pointer<span class="op">:</span></span>
<span id="cb16-18"><a href="#cb16-18"></a><span class="st">            </span><span class="cf">if</span> q.val <span class="op">&lt;</span><span class="st"> </span>pointer.val and p.val <span class="op">&lt;</span><span class="st"> </span>pointer.val<span class="op">:</span></span>
<span id="cb16-19"><a href="#cb16-19"></a><span class="st">                </span>pointer =<span class="st"> </span>pointer.left</span>
<span id="cb16-20"><a href="#cb16-20"></a>            elif q.val <span class="op">&gt;</span><span class="st"> </span>pointer.val and p.val <span class="op">&gt;</span><span class="st"> </span>pointer.val<span class="op">:</span></span>
<span id="cb16-21"><a href="#cb16-21"></a><span class="st">                </span>pointer =<span class="st"> </span>pointer.right</span>
<span id="cb16-22"><a href="#cb16-22"></a>            <span class="cf">else</span><span class="op">:</span></span>
<span id="cb16-23"><a href="#cb16-23"></a><span class="st">                </span>return pointer</span></code></pre></div>
</div>
<div id="二叉树的所有路径" class="section level3">
<h3><span class="header-section-number">1.4.12</span> 二叉树的所有路径</h3>
<div class="figure">
<img src="figs/所有路径.png" alt="" />
<p class="caption">所有路径</p>
</div>
<div class="sourceCode" id="cb17"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb17-1"><a href="#cb17-1"></a>class <span class="kw">Solution</span>(object)<span class="op">:</span></span>
<span id="cb17-2"><a href="#cb17-2"></a><span class="st">    </span>def <span class="kw">binaryTreePaths</span>(self, root)<span class="op">:</span></span>
<span id="cb17-3"><a href="#cb17-3"></a><span class="st">        &quot;&quot;&quot;</span></span>
<span id="cb17-4"><a href="#cb17-4"></a><span class="st">        :type root: TreeNode</span></span>
<span id="cb17-5"><a href="#cb17-5"></a><span class="st">        :rtype: List[str]</span></span>
<span id="cb17-6"><a href="#cb17-6"></a><span class="st">        &quot;&quot;&quot;</span></span>
<span id="cb17-7"><a href="#cb17-7"></a>        result =<span class="st"> </span><span class="kw">list</span>()</span>
<span id="cb17-8"><a href="#cb17-8"></a>        <span class="cf">if</span> root <span class="op">==</span><span class="st"> </span>None<span class="op">:</span></span>
<span id="cb17-9"><a href="#cb17-9"></a><span class="st">            </span>return result</span>
<span id="cb17-10"><a href="#cb17-10"></a></span>
<span id="cb17-11"><a href="#cb17-11"></a>        <span class="cf">if</span> root.left <span class="op">==</span><span class="st"> </span>None and root.right <span class="op">==</span><span class="st"> </span>None<span class="op">:</span></span>
<span id="cb17-12"><a href="#cb17-12"></a><span class="st">            </span><span class="kw">result.append</span>(<span class="kw">str</span>(root.val))</span>
<span id="cb17-13"><a href="#cb17-13"></a>            return result <span class="co"># 保存根节点的值</span></span>
<span id="cb17-14"><a href="#cb17-14"></a></span>
<span id="cb17-15"><a href="#cb17-15"></a>        left =<span class="st"> </span><span class="kw">self.binaryTreePaths</span>(root.left)</span>
<span id="cb17-16"><a href="#cb17-16"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="kw">len</span>(left))<span class="op">:</span></span>
<span id="cb17-17"><a href="#cb17-17"></a><span class="st">            </span><span class="kw">result.append</span>(<span class="kw">str</span>(root.val) <span class="op">+</span><span class="st"> &#39;-&gt;&#39;</span> <span class="op">+</span><span class="st"> </span>left[i]) <span class="co">#遍历一遍左节点</span></span>
<span id="cb17-18"><a href="#cb17-18"></a></span>
<span id="cb17-19"><a href="#cb17-19"></a>        right =<span class="st"> </span><span class="kw">self.binaryTreePaths</span>(root.right) <span class="co">#遍历一遍右节点</span></span>
<span id="cb17-20"><a href="#cb17-20"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="kw">len</span>(right))<span class="op">:</span></span>
<span id="cb17-21"><a href="#cb17-21"></a><span class="st">            </span><span class="kw">result.append</span>(<span class="kw">str</span>(root.val) <span class="op">+</span><span class="st"> &#39;-&gt;&#39;</span> <span class="op">+</span><span class="st"> </span>right[i])</span>
<span id="cb17-22"><a href="#cb17-22"></a></span>
<span id="cb17-23"><a href="#cb17-23"></a>        return result</span></code></pre></div>
</div>
<div id="左叶子之和" class="section level3">
<h3><span class="header-section-number">1.4.13</span> 左叶子之和</h3>
<div class="figure">
<img src="figs/左叶子之和.png" alt="" />
<p class="caption">左叶子之和</p>
</div>
<p>也就是左子树的叶子节点的值与右子树左叶子叶子节点的值</p>
<div class="sourceCode" id="cb18"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb18-1"><a href="#cb18-1"></a>class <span class="kw">Solution</span>(object)<span class="op">:</span></span>
<span id="cb18-2"><a href="#cb18-2"></a><span class="st">    </span>def <span class="kw">sumOfLeftLeaves</span>(self, root)<span class="op">:</span></span>
<span id="cb18-3"><a href="#cb18-3"></a><span class="st">        &quot;&quot;&quot;</span></span>
<span id="cb18-4"><a href="#cb18-4"></a><span class="st">        :type root: TreeNode</span></span>
<span id="cb18-5"><a href="#cb18-5"></a><span class="st">        :rtype: int</span></span>
<span id="cb18-6"><a href="#cb18-6"></a><span class="st">        &quot;&quot;&quot;</span></span>
<span id="cb18-7"><a href="#cb18-7"></a>        result =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb18-8"><a href="#cb18-8"></a>        <span class="cf">if</span> not root<span class="op">:</span></span>
<span id="cb18-9"><a href="#cb18-9"></a><span class="st">            </span>return <span class="dv">0</span>      </span>
<span id="cb18-10"><a href="#cb18-10"></a>        <span class="cf">if</span> root.left and not root.left.left and not root.left.right<span class="op">:</span></span>
<span id="cb18-11"><a href="#cb18-11"></a><span class="st">            </span>result <span class="op">+</span><span class="er">=</span><span class="st"> </span>root.left.val</span>
<span id="cb18-12"><a href="#cb18-12"></a>        return result<span class="op">+</span><span class="kw">self.sumOfLeftLeaves</span>(root.left)<span class="op">+</span><span class="kw">self.sumOfLeftLeaves</span>(root.right) </span></code></pre></div>
</div>
<div id="路径总和-1" class="section level3">
<h3><span class="header-section-number">1.4.14</span> 路径总和</h3>
<div class="figure">
<img src="figs/路径总和.png" alt="" />
<p class="caption">路径总和</p>
</div>
<p>利用递归，当root为None时，返回False，当root的值等于sum且root为叶节点时，返回true，如果不相等，往下递归，只要左子树和右子树有一条路径即可返回True</p>
<div class="sourceCode" id="cb19"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb19-1"><a href="#cb19-1"></a>class <span class="kw">Solution</span>(object)<span class="op">:</span></span>
<span id="cb19-2"><a href="#cb19-2"></a><span class="st">    </span>def <span class="kw">pathSum</span>(self, root, sum)<span class="op">:</span></span>
<span id="cb19-3"><a href="#cb19-3"></a><span class="st">        &quot;&quot;&quot;</span></span>
<span id="cb19-4"><a href="#cb19-4"></a><span class="st">        :type root: TreeNode</span></span>
<span id="cb19-5"><a href="#cb19-5"></a><span class="st">        :type sum: int</span></span>
<span id="cb19-6"><a href="#cb19-6"></a><span class="st">        :rtype: int</span></span>
<span id="cb19-7"><a href="#cb19-7"></a><span class="st">        &quot;&quot;&quot;</span></span>
<span id="cb19-8"><a href="#cb19-8"></a>        <span class="cf">if</span> not root<span class="op">:</span></span>
<span id="cb19-9"><a href="#cb19-9"></a><span class="st">            </span>return <span class="dv">0</span></span>
<span id="cb19-10"><a href="#cb19-10"></a>        return <span class="kw">self.pathSumFrom</span>(root, sum) <span class="op">+</span><span class="st"> </span><span class="kw">self.pathSum</span>(root.left, sum) <span class="op">+</span><span class="st"> </span><span class="kw">self.pathSum</span>(root.right, sum)</span>
<span id="cb19-11"><a href="#cb19-11"></a></span>
<span id="cb19-12"><a href="#cb19-12"></a>    def <span class="kw">pathSumFrom</span>(self, node, sum)<span class="op">:</span></span>
<span id="cb19-13"><a href="#cb19-13"></a><span class="st">        </span><span class="cf">if</span> not node<span class="op">:</span></span>
<span id="cb19-14"><a href="#cb19-14"></a><span class="st">            </span>return <span class="dv">0</span></span>
<span id="cb19-15"><a href="#cb19-15"></a>        <span class="kw">return</span> (<span class="dv">1</span> <span class="cf">if</span> node.val <span class="op">==</span><span class="st"> </span>sum <span class="cf">else</span> <span class="dv">0</span>) <span class="op">+</span><span class="st"> </span><span class="kw">self.pathSumFrom</span>(node.left, sum <span class="op">-</span><span class="st"> </span>node.val) <span class="op">+</span><span class="st"> </span><span class="kw">self.pathSumFrom</span>(node.right, sum <span class="op">-</span><span class="st"> </span>node.val)</span></code></pre></div>
</div>
</div>
<div id="动态规划问题" class="section level2">
<h2><span class="header-section-number">1.5</span> 动态规划问题</h2>
<p>感觉一维考的多一些，至少看经验贴是这样</p>
<p>动态规划问题</p>
<p><strong>解题思路</strong>：状态定义，转移方程，初始条件，返回值</p>
<div id="买卖股票的最佳时机" class="section level3">
<h3><span class="header-section-number">1.5.1</span> 买卖股票的最佳时机</h3>
<p>买股票的的价格不能低于买股票的，这是一个约束条件</p>
<p>给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。</p>
<p>如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。</p>
<p>注意：你不能在买入股票前卖出股票。</p>
<p> 
示例 1:</p>
<p>输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。</p>
<div class="sourceCode" id="cb20"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb20-1"><a href="#cb20-1"></a>class Solution<span class="op">:</span></span>
<span id="cb20-2"><a href="#cb20-2"></a><span class="st">    </span>def <span class="kw">maxProfit</span>(self, prices<span class="op">:</span><span class="st"> </span>List[int]) -&gt;<span class="st"> </span>int<span class="op">:</span></span>
<span id="cb20-3"><a href="#cb20-3"></a><span class="st">        </span>inf =<span class="st"> </span><span class="kw">int</span>(<span class="fl">1e9</span>)</span>
<span id="cb20-4"><a href="#cb20-4"></a>        minprice =<span class="st"> </span>inf  <span class="co">#用一个值来维护历史最低价格</span></span>
<span id="cb20-5"><a href="#cb20-5"></a>        maxprofit =<span class="st"> </span><span class="dv">0</span> <span class="co">#利润不能小于0</span></span>
<span id="cb20-6"><a href="#cb20-6"></a>        <span class="cf">for</span> price <span class="cf">in</span> prices<span class="op">:</span></span>
<span id="cb20-7"><a href="#cb20-7"></a><span class="st">            </span>maxprofit =<span class="st"> </span><span class="kw">max</span>(price <span class="op">-</span><span class="st"> </span>minprice, maxprofit)</span>
<span id="cb20-8"><a href="#cb20-8"></a>            minprice =<span class="st"> </span><span class="kw">min</span>(price, minprice)</span>
<span id="cb20-9"><a href="#cb20-9"></a>        return maxprofit</span></code></pre></div>
</div>
<div id="爬楼梯问题" class="section level3">
<h3><span class="header-section-number">1.5.2</span> 爬楼梯问题</h3>
<p>斐波那契数列：只需要考虑最后到达最后一阶实现的几种情况</p>
<p>题目一般有2种，可以爬2阶或者3阶，思路一样，递归+DP，但是要注意时间复杂度。。</p>
</div>
<div id="最大子序和问题" class="section level3">
<h3><span class="header-section-number">1.5.3</span> 最大子序和问题</h3>
<p>给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。</p>
<p>示例:</p>
<p>输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。</p>
<p>动态规划的入门篇的题</p>
<div class="sourceCode" id="cb21"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb21-1"><a href="#cb21-1"></a>class Solution<span class="op">:</span></span>
<span id="cb21-2"><a href="#cb21-2"></a><span class="st">    </span>def <span class="kw">maxSubArray</span>(self,nums<span class="op">:</span>List[int])-&gt;int<span class="op">:</span></span>
<span id="cb21-3"><a href="#cb21-3"></a><span class="st">        </span><span class="cf">if</span> <span class="kw">len</span>(nums)<span class="op">==</span><span class="dv">0</span><span class="op">:</span></span>
<span id="cb21-4"><a href="#cb21-4"></a><span class="st">            </span>return <span class="dv">0</span></span>
<span id="cb21-5"><a href="#cb21-5"></a>        <span class="cf">if</span> <span class="kw">len</span>(nums)<span class="op">==</span><span class="dv">1</span><span class="op">:</span></span>
<span id="cb21-6"><a href="#cb21-6"></a><span class="st">            </span>range nums[<span class="dv">0</span>]</span>
<span id="cb21-7"><a href="#cb21-7"></a></span>
<span id="cb21-8"><a href="#cb21-8"></a>        res=nums[<span class="dv">0</span>]</span>
<span id="cb21-9"><a href="#cb21-9"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">1</span>,<span class="kw">len</span>(nums))<span class="op">:</span></span>
<span id="cb21-10"><a href="#cb21-10"></a><span class="st">            </span>nums[i]=<span class="kw">max</span>(nums[i],nums[i]<span class="op">+</span>nums[<span class="op">-</span><span class="dv">1</span>])</span>
<span id="cb21-11"><a href="#cb21-11"></a></span>
<span id="cb21-12"><a href="#cb21-12"></a>            res=<span class="kw">max</span>(res,num[i])</span>
<span id="cb21-13"><a href="#cb21-13"></a>        return res</span></code></pre></div>
</div>
<div id="偷钱问题" class="section level3">
<h3><span class="header-section-number">1.5.4</span> 偷钱问题</h3>
<p>你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。</p>
<p>给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。</p>
<p>示例 1:</p>
<p>输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
  偷窃到的最高金额 = 1 + 3 = 4 。</p>
<div class="sourceCode" id="cb22"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb22-1"><a href="#cb22-1"></a>class Solution<span class="op">:</span></span>
<span id="cb22-2"><a href="#cb22-2"></a><span class="st">    </span>def <span class="kw">rob</span>(self, nums<span class="op">:</span><span class="st"> </span>List[int]) -&gt;<span class="st"> </span>int<span class="op">:</span></span>
<span id="cb22-3"><a href="#cb22-3"></a><span class="st">       </span>prev =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb22-4"><a href="#cb22-4"></a>       curr =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb22-5"><a href="#cb22-5"></a>    </span>
<span id="cb22-6"><a href="#cb22-6"></a>     <span class="co"># 每次循环，计算“偷到当前房子为止的最大金额”</span></span>
<span id="cb22-7"><a href="#cb22-7"></a>       <span class="cf">for</span> i <span class="cf">in</span> nums<span class="op">:</span></span>
<span id="cb22-8"><a href="#cb22-8"></a><span class="st">        </span><span class="co"># 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]</span></span>
<span id="cb22-9"><a href="#cb22-9"></a><span class="st">        </span><span class="co"># dp[k] = max{ dp[k-1], dp[k-2] + i }</span></span>
<span id="cb22-10"><a href="#cb22-10"></a><span class="st">           </span>prev, curr =<span class="st"> </span>curr, <span class="kw">max</span>(curr, prev <span class="op">+</span><span class="st"> </span>i)</span>
<span id="cb22-11"><a href="#cb22-11"></a>        <span class="co"># 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]</span></span>
<span id="cb22-12"><a href="#cb22-12"></a></span>
<span id="cb22-13"><a href="#cb22-13"></a>       return curr</span></code></pre></div>
</div>
<div id="比特位计数" class="section level3">
<h3><span class="header-section-number">1.5.5</span> 比特位计数</h3>
<p>给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。</p>
<p>示例 1:</p>
<p>输入: 2
输出: [0,1,1] ** 返回0，1，2三个数的二进制种的1的数目**
示例 2:</p>
<p>输入: 5
输出: [0,1,1,2,1,2]</p>
<p>对于所有的数字，只有两类：</p>
<p>奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
举例：
0 = 0 1 = 1
2 = 10 3 = 11
偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
举例：
2 = 10 4 = 100 8 = 1000
3 = 11 6 = 110 12 = 1100
另外，0 的 1 个数为 0，于是就可以根据奇偶性开始遍历计算了。</p>
<div class="sourceCode" id="cb23"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb23-1"><a href="#cb23-1"></a>class Solution<span class="op">:</span></span>
<span id="cb23-2"><a href="#cb23-2"></a><span class="st">    </span>def <span class="kw">countBits</span>(self, num<span class="op">:</span><span class="st"> </span>int) -&gt;<span class="st"> </span>List[int]<span class="op">:</span></span>
<span id="cb23-3"><a href="#cb23-3"></a><span class="st">        </span>ret =<span class="st"> </span>[<span class="dv">0</span>, <span class="dv">1</span>, <span class="dv">1</span>]</span>
<span id="cb23-4"><a href="#cb23-4"></a>        <span class="cf">for</span> n <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">3</span>, num<span class="op">+</span><span class="dv">1</span>)<span class="op">:</span></span>
<span id="cb23-5"><a href="#cb23-5"></a><span class="st">            </span><span class="kw">ret.append</span>(ret[<span class="op">-</span><span class="dv">1</span>]<span class="op">+</span><span class="dv">1</span>) <span class="cf">if</span> n <span class="op">&amp;</span><span class="st"> </span><span class="dv">1</span> <span class="op">==</span><span class="st"> </span><span class="dv">1</span> <span class="cf">else</span> <span class="kw">ret.append</span>(ret[n<span class="op">/</span><span class="er">/</span><span class="dv">2</span>])</span>
<span id="cb23-6"><a href="#cb23-6"></a>        return ret[<span class="dv">0</span><span class="op">:</span>num<span class="op">+</span><span class="dv">1</span>]</span></code></pre></div>
</div>
<div id="最短路径和问题" class="section level3">
<h3><span class="header-section-number">1.5.6</span> 最短路径和问题</h3>
<p>给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。</p>
<p>说明：每次只能向下或者向右移动一步。</p>
<p>示例:</p>
<p>输入:
[
  [1,3,1],
[1,5,1],
[4,2,1]]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。</p>
<p><img src="figs/最短路径和的问题.png" alt="最短路径和的问题" />
二维的动态规划</p>
<p>i横向,j纵向</p>
<div class="sourceCode" id="cb24"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb24-1"><a href="#cb24-1"></a>class Solution<span class="op">:</span></span>
<span id="cb24-2"><a href="#cb24-2"></a><span class="st">    </span>def <span class="kw">minPathSum</span>(self, grid<span class="op">:</span><span class="st"> </span>[[int]]) -&gt;<span class="st"> </span>int<span class="op">:</span></span>
<span id="cb24-3"><a href="#cb24-3"></a><span class="st">        </span><span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="kw">len</span>(grid))<span class="op">:</span></span>
<span id="cb24-4"><a href="#cb24-4"></a><span class="st">            </span><span class="cf">for</span> j <span class="cf">in</span> <span class="kw">range</span>(<span class="kw">len</span>(grid[<span class="dv">0</span>]))<span class="op">:</span></span>
<span id="cb24-5"><a href="#cb24-5"></a><span class="st">                </span><span class="cf">if</span> i <span class="op">==</span><span class="st"> </span>j <span class="op">==</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span><span class="st"> </span>continue</span>
<span id="cb24-6"><a href="#cb24-6"></a>                elif i <span class="op">==</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span><span class="st">  </span>grid[i][j] =<span class="st"> </span>grid[i][j <span class="op">-</span><span class="st"> </span><span class="dv">1</span>] <span class="op">+</span><span class="st"> </span>grid[i][j]</span>
<span id="cb24-7"><a href="#cb24-7"></a>                elif j <span class="op">==</span><span class="st"> </span><span class="dv">0</span><span class="op">:</span><span class="st">  </span>grid[i][j] =<span class="st"> </span>grid[i <span class="op">-</span><span class="st"> </span><span class="dv">1</span>][j] <span class="op">+</span><span class="st"> </span>grid[i][j]</span>
<span id="cb24-8"><a href="#cb24-8"></a>                <span class="cf">else</span><span class="op">:</span><span class="st"> </span>grid[i][j] =<span class="st"> </span><span class="kw">min</span>(grid[i <span class="op">-</span><span class="st"> </span><span class="dv">1</span>][j], grid[i][j <span class="op">-</span><span class="st"> </span><span class="dv">1</span>]) <span class="op">+</span><span class="st"> </span>grid[i][j]</span>
<span id="cb24-9"><a href="#cb24-9"></a>        return grid[<span class="op">-</span><span class="dv">1</span>][<span class="op">-</span><span class="dv">1</span>]</span></code></pre></div>
</div>
<div id="回文字符串" class="section level3">
<h3><span class="header-section-number">1.5.7</span> 回文字符串</h3>
<p>这个之前参加某个笔试遇到了</p>
<p>给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。</p>
<p>示例 1：</p>
<p>输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：</p>
<p>输入: “cbbd”
输出: “bb”</p>
<p>解题思路
<img src="figs/最长回文字符串.png" alt="最长回文字符串" /></p>
<div class="sourceCode" id="cb25"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb25-1"><a href="#cb25-1"></a>class Solution<span class="op">:</span></span>
<span id="cb25-2"><a href="#cb25-2"></a><span class="st">    </span>def <span class="kw">longestPalindrome</span>(self, s<span class="op">:</span><span class="st"> </span>str) -&gt;<span class="st"> </span>str<span class="op">:</span></span>
<span id="cb25-3"><a href="#cb25-3"></a><span class="st">        </span><span class="co">#dp[i][j] = true,if s[i] = s[j]</span></span>
<span id="cb25-4"><a href="#cb25-4"></a><span class="st">        </span><span class="co">#dp[0][len(s)-1]</span></span>
<span id="cb25-5"><a href="#cb25-5"></a><span class="st">        </span>length =<span class="st"> </span><span class="kw">len</span>(s)</span>
<span id="cb25-6"><a href="#cb25-6"></a>        dp =<span class="st"> </span>[[<span class="dv">0</span>] <span class="op">*</span><span class="st"> </span>length <span class="cf">for</span> _ <span class="cf">in</span> <span class="kw">range</span>(<span class="kw">len</span>(s))]</span>
<span id="cb25-7"><a href="#cb25-7"></a>        res =<span class="st"> </span><span class="dv">0</span>, <span class="dv">0</span> <span class="co">#长度为1时</span></span>
<span id="cb25-8"><a href="#cb25-8"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(<span class="dv">1</span>, length)<span class="op">:</span></span>
<span id="cb25-9"><a href="#cb25-9"></a><span class="st">             </span><span class="cf">for</span> j <span class="cf">in</span> <span class="kw">range</span>(length<span class="op">-</span>i)<span class="op">:</span></span>
<span id="cb25-10"><a href="#cb25-10"></a><span class="st">                </span><span class="cf">if</span> s[j] <span class="op">==</span><span class="st"> </span>s[j<span class="op">+</span>i] <span class="kw">and</span> (j<span class="op">+</span><span class="dv">1</span> <span class="op">&gt;=</span><span class="st"> </span>j<span class="op">+</span>i<span class="dv">-1</span> or dp[j<span class="op">+</span><span class="dv">1</span>][j<span class="op">+</span>i<span class="dv">-1</span>])<span class="op">:</span></span>
<span id="cb25-11"><a href="#cb25-11"></a><span class="st">                    </span>dp[j][j<span class="op">+</span>i] =<span class="st"> </span><span class="dv">1</span> </span>
<span id="cb25-12"><a href="#cb25-12"></a>                    res =<span class="st"> </span>j, j<span class="op">+</span>i</span>
<span id="cb25-13"><a href="#cb25-13"></a>        left, right =<span class="st"> </span>res</span>
<span id="cb25-14"><a href="#cb25-14"></a>        return s[left<span class="op">:</span><span class="st"> </span>right<span class="op">+</span><span class="dv">1</span>]</span></code></pre></div>
<p>动态规划问题解题思路</p>
<div class="figure">
<img src="figs/动态规划问题解题思路.png" alt="" />
<p class="caption">动态规划问题解题思路</p>
</div>
</div>
</div>
<div id="哈希表" class="section level2">
<h2><span class="header-section-number">1.6</span> 哈希表</h2>
<p>python中的字典的原理</p>
<p><strong>前缀</strong></p>
<p>使用前缀数组的一大好处是可用 pre(b) - pre(a-1) 来表示 a-&gt;b 中这段中数组的和。这个 a-1 可以不用那么纠结。重点理解思想。</p>
<p>比如 前5项的和 - 前3项的和 = 第4项~第5项的和。 (1+2+3+4+5) - (1+2+3) = 4+5</p>
<p>这个前缀和数组 preSum 的含义也很好理解，preSum[i] 就是 nums[0..i-1] 的和。那么如果我们想求 nums[i..j] 的和，只需要一步操作 preSum[j+1]-preSum[i] 即可，而不需要重新去遍历数组了。</p>
<div id="k数之和" class="section level3">
<h3><span class="header-section-number">1.6.1</span> K数之和</h3>
<p>给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。</p>
<p>示例 1 :</p>
<p>输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :</p>
<p>数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。</p>
<p>这道题刚开始想到的思路是，先利用dp数组存放前i个数的和（前缀和），然后遍历这个数组，对于每个元素，求出dp[i]+k在dp[i:]的存在个数，即为以i+1开头的符合条件的子数组的个数，遍历结束把每个点的个数加在一起，即为答案。</p>
<p>分析可知，这种方法除了开始生成dp遍历了一次数组，在后面使用了双层循环，时间复杂度O(N^2)，空间复杂度O(N)。</p>
<p>这种方法可以通过，但是耗时太多，那么，如果对时间复杂度进行优化呢。</p>
<p>==</p>
<p>使用哈希表（Python中字典原理）即可。抛弃dp数组，<strong>只使用一个变量pre来保存当前位置的前缀和，使用一个字典dp，它的key是前缀和的值，对应的value表示这个前缀和出现的次数。</strong></p>
<p>在元素累加的过程中得到sum[j]=nums[0]+nums[1]+···+nums[j]，并放入哈希表中。如果我们可以在哈希表中发现之前存在着sum[i]使得sum[j]-sum[i]=k，那么也就说明了有一个子序列之和为 k。时间复杂度终于被降到了<span class="math inline">\(O(n)\)</span>。</p>
<p>首先添加dp[0] = 1，表示前缀和为0的情况出现了一次(这是为了考虑从i=0开始的答案)，之后遍历数组，计算前缀和pre，加入dp（要判断pre是否存在，不存在写入，存在dp[pre]+=1)，同时判断pre-k是否在dp字典中，如果在，ans+=dp[pre-k]，说明存在dp[pre-k]种答案。最后返回ans即可。</p>
<p>。
这种情况只遍历了一次数组，字典中找值的过程时间复杂度O(1)，所以总的时间复杂度O(N)，只用到了一个变量和字典，空间复杂度O(N)。</p>
<div class="sourceCode" id="cb26"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb26-1"><a href="#cb26-1"></a>class Solution<span class="op">:</span></span>
<span id="cb26-2"><a href="#cb26-2"></a><span class="st">    </span>def <span class="kw">subarraySum</span>(self, nums<span class="op">:</span><span class="st"> </span>List[int], k<span class="op">:</span><span class="st"> </span>int) -&gt;<span class="st"> </span>int<span class="op">:</span></span>
<span id="cb26-3"><a href="#cb26-3"></a><span class="st">        </span>n =<span class="st"> </span><span class="kw">len</span>(nums)</span>
<span id="cb26-4"><a href="#cb26-4"></a>        pre =<span class="st"> </span><span class="dv">0</span> <span class="co">#前缀和</span></span>
<span id="cb26-5"><a href="#cb26-5"></a>        ans =<span class="st"> </span><span class="dv">0</span></span>
<span id="cb26-6"><a href="#cb26-6"></a>        dp =<span class="st"> </span><span class="kw">dict</span>() <span class="co">#存放 前缀和:出现次数，键值对，初始化一个0:1，为了考虑到从头开始到某点的子数组正好为答案。</span></span>
<span id="cb26-7"><a href="#cb26-7"></a>        dp[<span class="dv">0</span>] =<span class="st"> </span><span class="dv">1</span></span>
<span id="cb26-8"><a href="#cb26-8"></a>        <span class="cf">for</span> i <span class="cf">in</span> <span class="kw">range</span>(n)<span class="op">:</span></span>
<span id="cb26-9"><a href="#cb26-9"></a><span class="st">            </span>pre <span class="op">+</span><span class="er">=</span><span class="st"> </span>nums[i] <span class="co">#计算前缀和</span></span>
<span id="cb26-10"><a href="#cb26-10"></a>            <span class="cf">if</span> pre<span class="op">-</span>k <span class="cf">in</span> dp<span class="op">:</span><span class="st"> </span><span class="co">#如果pre-k这个前缀存在，那么答案加上它出现的次数</span></span>
<span id="cb26-11"><a href="#cb26-11"></a><span class="st">                </span>ans <span class="op">+</span><span class="er">=</span><span class="st"> </span>dp[pre<span class="op">-</span>k]</span>
<span id="cb26-12"><a href="#cb26-12"></a>            <span class="cf">if</span> pre <span class="cf">in</span> dp<span class="op">:</span><span class="st"> </span><span class="co">#更新dp[pre]</span></span>
<span id="cb26-13"><a href="#cb26-13"></a><span class="st">                </span>dp[pre] <span class="op">+</span><span class="er">=</span><span class="st"> </span><span class="dv">1</span></span>
<span id="cb26-14"><a href="#cb26-14"></a>            <span class="cf">else</span><span class="op">:</span></span>
<span id="cb26-15"><a href="#cb26-15"></a><span class="st">                </span>dp[pre] =<span class="st"> </span><span class="dv">1</span></span>
<span id="cb26-16"><a href="#cb26-16"></a>        return ans</span></code></pre></div>
</div>
</div>
<div id="贪心算法" class="section level2">
<h2><span class="header-section-number">1.7</span> 贪心算法</h2>
<div id="跳跃游戏" class="section level3">
<h3><span class="header-section-number">1.7.1</span> 跳跃游戏</h3>
<p>给定一个非负整数数组，你最初位于数组的第一个位置。</p>
<p>数组中的每个元素代表你在该位置可以跳跃的最大长度。</p>
<p>判断你是否能够到达最后一个位置。</p>
<p>示例 1:</p>
<p>输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。</p>
<p>示例 2:</p>
<p>输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。</p>
<ul>
<li>如果所有元素都不为0， 那么一定可以跳到最后；</li>
<li>从后往前开始想，如果这个节点能够达到，那么下一个节点只要大于等于1就行，如果这个节点不能达到那么那么期待下一个节点要大于等于能达到的距离</li>
</ul>
<p>可以用贪心的方法解决这个问题。</p>
<div class="figure">
<img src="figs/跳跃游戏.png" alt="" />
<p class="caption">跳跃游戏</p>
</div>
<div class="sourceCode" id="cb27"><pre class="sourceCode r"><code class="sourceCode r"><span id="cb27-1"><a href="#cb27-1"></a>class Solution<span class="op">:</span></span>
<span id="cb27-2"><a href="#cb27-2"></a><span class="st">    </span>def <span class="kw">canJump</span>(self, nums) <span class="op">:</span></span>
<span id="cb27-3"><a href="#cb27-3"></a><span class="st">        </span>max_i =<span class="st"> </span><span class="dv">0</span>       <span class="co">#初始化当前能到达最远的位置</span></span>
<span id="cb27-4"><a href="#cb27-4"></a>        <span class="cf">for</span> i, jump <span class="cf">in</span> <span class="kw">enumerate</span>(nums)<span class="op">:</span><span class="st">   </span><span class="co">#i为当前位置，jump是当前位置的跳数</span></span>
<span id="cb27-5"><a href="#cb27-5"></a><span class="st">            </span><span class="cf">if</span> max_i<span class="op">&gt;=</span>i and i<span class="op">+</span>jump<span class="op">&gt;</span>max_i<span class="op">:</span><span class="st">  </span><span class="co">#如果当前位置能到达，并且当前位置+跳数&gt;最远位置  </span></span>
<span id="cb27-6"><a href="#cb27-6"></a><span class="st">                </span>max_i =<span class="st"> </span>i<span class="op">+</span>jump  <span class="co">#更新最远能到达位置</span></span>
<span id="cb27-7"><a href="#cb27-7"></a>        return max_i<span class="op">&gt;=</span>i</span></code></pre></div>
<p>时间复杂度：O(n)，其中 n 为数组的大小。只需要访问 nums 数组一遍，共n 个位置。</p>
<p>空间复杂度：O(1)，不需要额外的空间开销。</p>
</div>
</div>
</div>
<!--bookdown:body:end-->
            </section>

          </div>
        </div>
      </div>
<!--bookdown:link_prev-->
<!--bookdown:link_next-->
    </div>
  </div>
<!--bookdown:config-->

<!-- dynamically load mathjax for compatibility with self-contained -->
<script>
  (function () {
    var script = document.createElement("script");
    script.type = "text/javascript";
    var src = "true";
    if (src === "" || src === "true") src = "https://mathjax.rstudio.com/latest/MathJax.js?config=TeX-MML-AM_CHTML";
    if (location.protocol !== "file:")
      if (/^https?:/.test(src))
        src = src.replace(/^https?:/, '');
    script.src = src;
    document.getElementsByTagName("head")[0].appendChild(script);
  })();
</script>
</body>

</html>
